// 104 二叉树的最大深度
// 深度优先的写法
const maxDepth = (root) => {
  if (root == null) return 0;
  let res = 0
  const dfs = (n, l) => {
    if(!n) return
    if(!n.left && !n.right) {
      res = Math.max(res, l)
    }
    dfs(n.left, l+1)
    dfs(n.right, l+1)
  }
  dfs(root, 1)
  return res;
}
// 111 二叉树的最小深度
var minDepth = function(root) {
  if(!root) return 0;
  const q = [[root, 1]];
  while(q) {
      let [n, l] = q.shift()
      if(!n.left && !n.right){
          return l
      }else{
          n.left && q.push([n.left, l+1])
          n.right && q.push([n.right, l+1])
      }
  }
};
// 102 102. 二叉树的层序遍历
var levelOrder = function(root) {
  if(!root) return []
  let q = [[root, 0]]
  let res = []
  while(q.length) {
      let [n, l] = q.shift()
      if(!res[l]) {
          res[l] = []
      }
      res[l].push(n.val)
      if(n.left) q.push([n.left, l+1])
      if(n.right) q.push([n.right, l+1])
  }
  return res
};
// var levelOrder = function(root) {
//   if(!root) return []
//   let q = [root]
//   let res = []
//   while(q.length) {
//       let len = q.length
//       res.push([])
//       while(len--) {
//           let n = q.shift()
//           res[res.length-1].push(n.val)
//           if(n.left) q.push(n.left)
//           if(n.right) q.push(n.right)
//       }
//   }
//   return res
// };

// 94. 二叉树的中序遍历
var inorderTraversal = function(root) {
  let p = root
  let stack = []
  let res = []
  while(stack.length || p) {
      while(p) {
          stack.push(p)
          p = p.left
      }
      let n = stack.pop()
      res.push(n.val)
      p =  n.right
  }
  return res
};

// 112. 路径总和
var hasPathSum = function(root, sum) {
  if(!root) return false
  let flag = false
  const dfs = (node, num) => {
      if(!node.left && !node.right && num === sum) {
          flag = true
      }
      if(node.left) dfs(node.left, num+node.left.val)
      if(node.right) dfs(node.right, num+node.right.val)
  }
  dfs(root, root.val)
  return flag
};